/*
 * @Author: szx
 * @Date: 2021-11-13 12:57:18
 * @LastEditTime: 2021-11-13 13:46:33
 * @Description:
 * @FilePath: \leetcode\500-599\547\547.go
 */
package main

// func findCircleNum(isConnected [][]int) int {
// 	vis := make([]bool, len(isConnected))
// 	var dfs func(i int)
// 	dfs = func(i int) {
// 		vis[i] = true
// 		for to, conn := range isConnected[i] {
// 			if conn == 1 && !vis[to] {
// 				dfs(to)
// 			}
// 		}
// 	}
// 	cnt := 0
// 	for i, v := range vis {
// 		if !v {
// 			cnt++
// 			dfs(i)
// 		}
// 	}
// 	return cnt
// }

func findCircleNum(isConnected [][]int) (ans int) {
	n := len(isConnected)
	parent := make([]int, n)
	for i := range parent {
		parent[i] = i
	}
	// 查找，找到根节点
	var find func(int) int
	find = func(x int) int {
		if parent[x] != x {
			parent[x] = find(parent[x])
		}
		return parent[x]
	}
	// 合并，找到两个的根节点，然后把其中一个设为另一个的父节点
	union := func(from, to int) {
		parent[find(from)] = find(to)
	}

	for i, row := range isConnected {
		for j := i + 1; j < n; j++ {
			if row[j] == 1 {
				union(i, j)
			}
		}
	}
	for i, p := range parent {
		if i == p {
			ans++
		}
	}
	return
}
